1. Field of the Invention
The present invention generally relates to the art of circuits and systems comprising electrical shift registers using a particular code or counting sequence, and more specifically to a random number generating apparatus for an interface unit of a Carrier Sense with Multiple Access and Collision Detect (CSMA/CD) Ethernet data network.
2. Description of the Related Art
Electronic data networks are becoming increasing widespread for the communication of divergent types of data including computer coded text and graphics, voice and video. Such networks enable the interconnection of large numbers of computer workstations, telephone and television systems, video teleconferencing systems and other facilities over common data links or carriers.
Computer workstations are typically interconnected by local area networks (LAN) such as Ethernet, Token Ring, DECNet and RS-232, whereas metropolitan, national and international systems are interconnected by wide area networks (WAN) such as T1, V3.5 and FDDI.
LANs and WANs themselves can be interconnected by devices known as hubs, bridges and routers in an unlimited configuration. Although the distinction between these interconnection devices is becoming increasingly arbitrary, they are officially classified in accordance with the layer in the Open Systems Interconnection (OSI) model in which they operate.
Hubs interconnect devices using the Physical Layer, bridges utilize the Data Link layer whereas routers operate using the Network layer. Hubs and bridges generally act merely as switches or funnels, whereas routers perform higher level functions including selecting optimal routes through the network for transmission of data packets or cells on an individual basis, and performing network management tasks such as forcing diagnostics operations and controlling other routers or nodes. Whereas hubs and bridges generally operate on data which is formatted in a single protocol such as those listed above (uniprotocol), routers can typically identify and process data which can be in any one of several protocols (multiprotocol).
Interconnect devices, especially the more sophisticated routers, have typically been large, bulky and expensive units which operate at relatively low speed. As such, they limit the data throughput speed in the network in which they are installed. The reasons why routers have been so slow is that they are generally multichip units which transfer data being processed to and from Content Addressable Memory (CAM) chips which are separate from the processor, input/output (I/O) and other functional chips of the unit.
These transfer operations each require multiple system clock cycles which fundamentally limit the transfer speed. In addition, multiple latencies are present in the various paths by which data moves through the unit. The degree by which such latencies can be reduced, as well as the degree by which the size and cost of a multichip system can be reduced, are also fundamentally limited.
Ethernet is a network protocol embodying IEEE standard 802.3, which is more generically referred to as Carrier Sense with Multiple Access and Carrier Detect (CSMA/CD). Ethernet cores used in hubs and other devices comprise transmit backoff units which execute a truncated exponential backoff algorithm in response to a sensed collision condition (two or more nodes attempting to transmit data simultaneously). This algorithm utilizes a pseudo random number generator to generate a random number which designates a backoff time, or a time for which the transmit engine of the core should wait before attempting transmission.
If all of the cores in the network utilize the same type of pseudo random number generator, they will generate the same sequence of random numbers. If the random number generators of two or more cores become synchronized with each other, they will cause the associated cores to back off by the same times. This will cause the cores to continuously attempt to transmit at the same times. This condition is called "lockup", and can result in the cores generating collisions indefinitely, preventing any data from being transmitted over the network.
Asynchronous Transfer Mode (ATM) is a network protocol which is highly advantageous in that it enables high speed transmission of divergent types of data, including codes, video and voice. This is accomplished by breaking down the data to be transmitted into cells including 48 bit Conversion Sublayer Payload Data Unit (CS-PDUs) which contain the actual data, and a header and trailer. ATM can also be utilized as a universal protocol, replacing the protocols which are currently in use and are specific to LANs or WANs.
The header contains a virtual channel identifier and a virtual path identifier which identify the particular cell and its intended destination, and specify an optimal path through the network through which the cell should be routed to reach its destination. The header can also include numerous other information such as the type of data in the CS-PDU and attributes of the data, the sender and/or the destination.
The physical limitations discussed above regarding routers in general also applies to ATM routers, adapters and termination devices which interconnect an ATM network to a network node using a different protocol (or to a host such as a computer workstation). A major problem which is inhibiting the widespread deployment of ATM is that no single ATM protocol has been developed. A diverse assortment of ATM protocols have been developed by various manufacturers throughout the industry, some of which are so different as to be incompatible with each other. At least, the difference between protocols prevents the various higher level capabilities of the individual protocols from being universally utilized.
Congestion is a problem in all networks. This occurs when a large number of users feed data into the network at the same time. ATM cells need not be contiguous, so that computer coded data from one user can be interspersed with, for example, voice data from another user in a time divisioned manner. However, if too many users attempt to inject too much data into the network simultaneously, the bandwidth of the network can be exceeded resulting in substantial delays in data transmission, transmission errors and lost data.
Congestion is controlled by sensing the traffic in the network at the various nodes, sending special information packets between nodes to notify the other nodes of the magnitude and type of congestion, and delaying transmission of data at specified nodes in accordance with a predetermined congestion control algorithm.
ATM networks are relatively new, and the nature and patterns which congestion can take are not well understood. This makes it difficult to formulate and implement an effective congestion control algorithm. Similar to the variety of ATM protocols which are currently in use, a number of divergent congestion control algorithms have been devised and placed into service.
ATM routers, termination devices and other network elements are hardwired with the particular manufacturer's protocol and congestion control algorithm. Although it is likely that a universal ATM standard will be developed in the near future the multiprotocol problem will be eliminated, ATM systems will have to accommodate newly developed congestion control algorithms for an extended period of time until the nature of congestion can be well understood and handled. In the meantime, any changes to existing ATM systems require hard retooling, which is extremely time consuming and expensive.